W14. Unrestricted Computation

1. Theory

1.1 Grammar Rules and the Top of the Chomsky Hierarchy

1.1.1 Grammar as a Rewriting System

A formal grammar is a finite rewriting system used to generate strings of a language. It is written as

where is the set of nonterminal symbols, is the set of terminal symbols, is the set of production rules, and is the start symbol. Terminals are the symbols that may appear in final generated strings; nonterminals are temporary symbols that still need to be rewritten.

A derivation begins with and repeatedly applies productions until only terminals remain. If and , then belongs to the language generated by the grammar:

For context-sensitive and unrestricted grammars, the left-hand side of a rule may contain more than one symbol. This is the main difference from context-free grammars, where the left-hand side must be a single nonterminal.

1.1.2 Why Type 1 and Type 0 Matter

Regular and context-free grammars are powerful enough for many programming-language and parsing tasks, but they cannot express all natural counting constraints. For example, the language

requires three equal blocks. A pushdown automaton has one stack, so it can naturally compare two dependent quantities, such as the number of ’s and ’s, but it cannot in general enforce three simultaneous equalities. Context-sensitive grammars can express such languages because their rules can rewrite symbols depending on neighboring context and can preserve enough structure to perform several coordinated counting operations.

Type-0 grammars are even more general. They correspond to Turing Machines and therefore capture exactly the recursively enumerable languages. They are not primarily a convenient programming notation; they are important because they identify the boundary of what can be generated or accepted by mechanical computation.

1.2 Context-Sensitive Grammars

1.2.1 Formal Definition

A context-sensitive grammar (CSG) is a grammar in which every production rule has the form

where , , and . The symbols and are the context: they must remain unchanged while the nonterminal is rewritten as .

The restriction means that ordinary context-sensitive rules cannot erase symbols. Equivalently, context-sensitive grammars are usually viewed as non-contracting grammars: no rule decreases the length of the current sentential form. The only standard exception is the rule , which is allowed if never appears on the right-hand side of any production.

This non-erasing behavior is not a minor technical detail. It is what connects CSGs to machines with bounded memory: every derivation preserves or increases length, so the grammar cannot hide unbounded computation by repeatedly deleting and recreating information.

1.2.2 Rule Order and Dead Ends

As with other grammar types, production rules are not applied in a predefined order. A grammar is valid if every word in the target language has at least one successful derivation and no word outside the language has a successful terminal derivation. Some choices of rule order may lead to a dead end containing nonterminals that can no longer be rewritten. That does not invalidate the grammar, because grammar derivation is nondeterministic: we only require the existence of a successful derivation for each valid word.

When constructing a CSG, it is helpful to separate rules by role:

• generation rules create the correct amount of symbolic material;
• permutation rules reorder nonterminals into the required block order;
• terminalization rules convert nonterminals into terminals once the structure is ready.

The common pitfall is allowing terminalization too early in a way that produces invalid terminal strings. If early terminalization only creates dead ends, the grammar may still be correct; if it creates a terminal word outside the intended language, the grammar is wrong.

In the solved construction tasks below, some adjacent swaps are written in the compact non-contracting form, such as . This is the standard equivalent presentation of context-sensitive grammars. If the course requires the strict displayed form , each such swap can be expanded by the same helper-symbol method used in the example; for instance can be replaced by , , , and .

1.2.3 Example Pattern: Generating

A standard CSG for

uses and as obligations to later produce ’s and ’s. The rules are:

The first two rules generate one for each pair . Repeated use of creates a mixed string such as . The middle rules simulate a swap of past , eventually collecting all symbols before all symbols. The final rules convert the left-to-right block into .

For example, for :

The temporary symbols and exist because a direct swap is not in the strict context-sensitive form . The multi-step replacement performs the same reordering without decreasing length.

1.2.4 Linear Bounded Automata

Context-sensitive grammars correspond exactly to linear bounded automata (LBAs). An LBA is a nondeterministic Turing Machine whose head is restricted to the part of the tape occupied by the input, often delimited by end-markers. If the input has length , the working space is bounded by a linear function of .

The equivalence is:

Intuitively, an LBA has enough memory to mark, compare, and rearrange information across the whole input, but not enough to use arbitrary unbounded tape beyond the input. This places it strictly above pushdown automata and below unrestricted Turing Machines.

1.3 Unrestricted Grammars

1.3.1 Formal Definition

An unrestricted grammar is a grammar whose productions have the form

where and contains at least one nonterminal. Equivalently, . The left-hand side cannot be empty, because allowing would allow symbols to appear from nothing without any control.

Unlike context-sensitive grammars, unrestricted grammars may shorten strings, delete markers, and rewrite whole configurations. This makes them powerful enough to simulate arbitrary Turing Machine computations.

1.3.2 Example Pattern: A Shorter Grammar for

Because unrestricted grammars are not constrained by context-sensitive rule shape, the language

can be generated more directly:

The only structural difference from the CSG version is the direct swap . This rule is allowed in an unrestricted grammar because the left-hand side may be any nonempty string containing a nonterminal.

For :

1.3.3 Unrestricted Grammars and Turing Machines

Unrestricted grammars generate exactly the languages accepted by nondeterministic Turing Machines:

Since deterministic and nondeterministic Turing Machines recognize the same class of languages, we also have:

at the level of language recognition. A language in this class is called recursively enumerable or computably enumerable. If a string belongs to such a language, some Turing Machine eventually accepts it. If the string does not belong, the machine may reject or may run forever.

1.4 Nondeterministic Turing Machines

1.4.1 Transition Function

A nondeterministic Turing Machine has the same components as a deterministic one, but its transition function returns a finite set of possible moves instead of one move. In the multi-tape notation used in the course, the deterministic transition type is

For a nondeterministic Turing Machine, the transition function becomes

where denotes the finite powerset. Thus, from one configuration, the machine may have zero, one, or many possible next configurations.

1.4.2 Acceptance and Equivalence with DTMs

The acceptance condition is existential: an NTM accepts an input if at least one computation branch reaches an accepting state. Branches that reject or run forever do not matter if another branch accepts.

Nondeterminism does not increase the class of languages recognized by Turing Machines. A deterministic Turing Machine can simulate an NTM by exploring the computation tree breadth-first. Breadth-first simulation is important because a depth-first simulation could get stuck forever on one infinite branch and never discover an accepting branch at a finite depth.

Therefore, deterministic and nondeterministic Turing Machines have the same recognition power. The difference is not what they can recognize, but how naturally and efficiently some computations can be described.

1.5 Chomsky Hierarchy Summary

The Chomsky hierarchy classifies grammars by the form of their production rules. The four classes are nested:

Chomsky type	Grammar	Rule form	Language class	Minimal automaton
Type 3	Regular	or	Regular	Finite State Automaton
Type 2	Context-free		Context-free	Nondeterministic Pushdown Automaton
Type 1	Context-sensitive	,	Context-sensitive	Linear Bounded Automaton
Type 0	Unrestricted	,	Recursively enumerable	Turing Machine

The table should be read from bottom to top in terms of restriction and from top to bottom in terms of expressive power. Type 3 is the most restrictive and easiest to decide algorithmically. Type 0 is the least restrictive and reaches the full power of Turing-computable recognition.

1.6 The Halting Problem

1.6.1 Statement

The Halting Problem asks whether there is one general algorithm that, given an arbitrary program and an arbitrary input to that program, always decides whether the program eventually stops or runs forever. For a particular program and a particular input, we can often answer this question by inspection, testing, or mathematical reasoning. The impossibility result says something stronger: there is no universal method that works for all programs and all inputs.

In Turing Machine language, assume each machine has a Gödel number, or index, , and let be the partial function computed by the machine with index on input . The value means that the computation is undefined because the machine does not halt. The hypothetical halting decider would compute the total function

The word total is crucial: a decider must always halt with a yes-or-no answer. Running the program and waiting is not enough, because if the program does not halt, the waiting procedure also does not halt.

1.6.2 Why the Halting Problem Is Undecidable

The proof is a diagonalization argument based on self-reference. Suppose, for contradiction, that the total function is computable. Define

If were computable, then would also be computable, because it simply calls and then either halts with value or loops. Therefore would have some machine index , so .

Now evaluate . If , then by definition of , does not halt; but by definition of , , so it does halt. Contradiction. If , then by definition of , halts; but by definition of , , so it does not halt. Contradiction again. Hence the assumed computable decider cannot exist.

This is why no program can solve the halting question for every possible program and input. By the Church-Turing thesis, the impossibility for Turing Machines applies to ordinary computer programs as well.

1.6.3 Static Analysis and Self-Reference

The Halting Problem is a negative result about static analysis of a behavioral property. A program analyzer tries to answer facts about behavior before or without fully executing the program. Some static checks are decidable: for example, whether an arithmetic expression is well parenthesized can be decided by a pushdown automaton. But a universal static analyzer for nontermination cannot exist.

The intuitive programming proof follows the same self-reference. Assume a procedure halts can always decide whether p(x) halts. Then define a program that asks whether a program halts on itself and deliberately does the opposite: if the analyzer says it halts, loop forever; otherwise halt. Running that new program on itself produces a contradiction. This is not a quirk of a programming language; it is the same diagonalization argument expressed operationally.

1.6.4 Physical Computers and the Mathematical Model

Physical computers are finite physical systems. In the real world, a running program may eventually stop because of power loss, memory corruption, hardware failure, or the end of the physical system. The Halting Problem is not about these external accidents. It is about mathematical program behavior under the abstract machine model: does the computation terminate according to its own rules?

This distinction matters because theoretical computer science studies the limits of algorithms, not the reliability of hardware. A physical crash is not a mathematical solution to nontermination.

1.7 Rice’s Theorem and Software Verification

1.7.1 Semantic Program Properties

Rice’s theorem says that every nontrivial semantic property of programs is undecidable. A property is semantic if it concerns what the program computes or how it behaves, rather than surface syntax. A property is nontrivial if some programs have it and some programs do not.

Examples of semantic properties include “this program halts on every input”, “this program ever prints zero”, or “this program computes the same function as a given specification”. Rice’s theorem says there is no algorithm that always gives a correct yes-or-no answer for all programs for any such nontrivial behavioral property.

1.7.2 Consequences for Verification

Rice’s theorem explains why fully automatic software verification is impossible in the strongest possible sense. Verification tools must work around undecidability by using restrictions, approximations, annotations, type systems, bounded search, proof obligations, or conservative analyses.

This does not make verification useless. It means a verification tool must give up at least one ideal requirement: it may reject some correct programs, fail to prove some true property, require human guidance, restrict the programming language, or analyze only bounded executions. The fundamental impossibility is what forces verification to be engineering rather than a single complete automatic solution.

1.8 Decidability, Semidecidability, and Recursive Sets

1.8.1 Decision Problems

A decision problem is a problem with two possible answers: yes or no. Many computational questions can be phrased as membership questions: given an encoded object , does belong to a set ?

Examples include:

• Does a program terminate on a given input?
• Given a graph and a set of vertices , is a clique?
• Given axioms, rules, and a formula, is the formula provable?

This set-based viewpoint lets us define decidability using characteristic functions.

1.8.2 Recursive Sets

The characteristic function of a set is

A set is recursive, also called decidable, if and only if is computable by a total algorithm. In other words, membership in can always be decided in finite time.

Historically, computability theory was called recursion theory. The class of -recursive functions was later shown to coincide with the class of functions computable by Turing Machines, which is one of the foundations behind the Church-Turing thesis.

1.8.3 Recursively Enumerable Sets

A set is recursively enumerable (RE), also called semidecidable, if either or is the image of a total computable function :

This means that there is an effective enumeration of all elements of . If , then by enumerating the values of , we eventually find and can answer yes. If , the enumeration may continue forever, so we may never obtain a no answer.

The Halting Problem is the standard example: it is semidecidable because if a program halts, simulation eventually discovers that fact. It is not decidable because if the program does not halt, simulation gives no finite certificate of nontermination in general.

1.8.4 Recursive versus Recursively Enumerable

Every recursive set is recursively enumerable, but not every recursively enumerable set is recursive. Decidable is stronger than semidecidable because a decider must answer both yes and no, while a semidecision procedure only guarantees yes answers.

The key characterization is:

Here is the complement of . Intuitively, if both and its complement can be semidecided, then we can run both semidecision procedures in parallel. Exactly one must eventually answer yes, and that tells us whether or .

The corollary is that decidable sets are closed under complement. This mirrors earlier closure discussions: for limited models, complement closure is often a sign that both yes and no cases are effectively controllable.

1.8.5 The Landscape of Language Classes

The computability landscape extends the Chomsky hierarchy. Regular languages sit inside context-free languages, which sit inside context-sensitive languages. Context-sensitive languages are decidable because LBAs have bounded configuration spaces. Decidable languages sit inside recursively enumerable languages. Outside the recursively enumerable languages are languages that cannot even be recognized by a Turing Machine.

This hierarchy explains the phrase “with great power comes great uncomputability”. Turing Machines and Turing-complete programming languages are powerful because they permit unbounded computation, including loops. That same feature makes universal termination and many behavioral properties undecidable.

1.9 Total Computable Functions and Expressive Limits

The lecture ends with a deeper limitation: there is no recursively enumerable formalism that defines all and only the total computable functions. Let be the set of indexes of all total computable functions, with two intended properties:

• if , then is total;
• if is total and computable, then some computes .

Such a set is not recursively enumerable. The proof is by diagonalization. If all and only total computable functions could be effectively enumerated, one could construct a new total computable function that differs from the -th enumerated function on input , contradicting completeness of the enumeration.

The consequence is practical. Finite-state automata define only total computations, but not all total computable functions. Turing Machines define all computable functions, but also include partial functions that may not terminate. A Turing-complete language such as C can express every algorithmic behavior, including nonterminating behavior. There cannot be a recursively enumerable subset of C programs that captures exactly all terminating programs and excludes all nonterminating ones.

---

2. Definitions

• Grammar: A 4-tuple consisting of nonterminals, terminals, production rules, and a start symbol.
• Terminal symbol: A symbol that may appear in final generated strings and is not rewritten further.
• Nonterminal symbol: A temporary grammar symbol that can be rewritten using production rules.
• Production rule: A rewriting rule that replaces an occurrence of by during a derivation.
• Derivation: A sequence of rewriting steps starting from and ending, if successful, in a terminal string.
• Context-sensitive grammar: A Type-1 grammar whose rules have the form with , except possibly under the standard restriction.
• Non-contracting grammar: A grammar in which no production decreases the length of the current sentential form.
• Context: The surrounding strings and in a rule .
• Linear bounded automaton (LBA): A nondeterministic Turing Machine whose usable tape is bounded by the input region; LBAs recognize exactly the context-sensitive languages.
• Unrestricted grammar: A Type-0 grammar with productions where contains at least one nonterminal and is arbitrary.
• Nondeterministic Turing Machine (NTM): A Turing Machine whose transition function returns a finite set of possible next moves.
• Recursively enumerable language: A language accepted by a Turing Machine; members are eventually accepted, while non-members may cause nontermination.
• Chomsky hierarchy: The nested classification of grammar and language classes into regular, context-free, context-sensitive, and recursively enumerable.
• Dead end: A derivation branch that reaches a sentential form containing nonterminals but no useful rule sequence to a terminal word.
• Terminalization rule: A rule that converts a nonterminal marker into a terminal symbol.
• Halting Problem: The decision problem asking whether an arbitrary program or Turing Machine halts on an arbitrary input.
• Gödel number: A natural-number encoding of a program or Turing Machine, allowing machines and programs to be treated as data.
• Partial function: A function that may be undefined on some inputs, often because the corresponding computation does not halt.
• Total function: A function defined on every input in its domain; a decider computes a total yes-or-no function.
• Diagonalization: A proof technique that constructs an object differing from every object in a supposed complete enumeration, often by making a machine analyze itself.
• Static analysis: Analysis of program behavior without relying on fully executing the program on all possible runs.
• Rice’s theorem: The theorem stating that every nontrivial semantic property of programs is undecidable.
• Semantic property: A property about what a program computes or how it behaves, not merely how its text is written.
• Nontrivial property: A property that holds for at least one program and fails for at least one program.
• Decision problem: A computational problem whose answer is yes or no.
• Recursive set: A decidable set whose characteristic function is computable and total.
• Characteristic function: The function that returns for members of and for nonmembers.
• Semidecidable problem: A problem for which there is an algorithm that halts with yes on positive instances but may run forever on negative instances.
• Complement of a set: The set containing exactly the natural numbers not in .

---

3. Formulas

• Grammar tuple:
• Generated language:
• Context-sensitive rule form:
• Unrestricted rule form:
• NTM transition function:
• Chomsky hierarchy containment:
• Halting decider target function:
• Diagonal halting contradiction function:
• Characteristic function of a set:
• Recursively enumerable set as an image:
• Recursive iff set and complement are RE:

---

4. Practice

4.1. Generate with a Context-Sensitive Grammar (Lab 12, Example 1)

Generate

using a context-sensitive grammar.

Click to see the solution

Key Concept: First generate one and one pair of obligations for each value of , then reorder all symbols before all symbols, then convert the markers to terminals.

Use the grammar:

1. Generate the correct number of obligations. For : There are three ’s, three ’s, and three ’s.
2. Move symbols left of symbols. The sequence behaves like a context-sensitive swap of into .
3. After enough swaps, the mixed suffix becomes:
4. Convert symbols into symbols from left to right:
5. Convert symbols into symbols from left to right:

Answer: The grammar generates exactly for .

4.2. Construct a CSG for (Lab 12, Task 1)

Define a context-sensitive grammar for

Click to see the solution

Key Concept: The number of ’s must match the number of ’s, and the number of ’s must match the number of ’s. We generate markers for the block and markers for the block, then swap past until the order is .

Use terminals and nonterminals . The grammar is:

1. Generate the and counts. Applying repeatedly and then produces:
2. Generate the and counts. Applying repeatedly and then produces:
3. Reorder the marker blocks. The rule moves every to the right of every :
4. Terminalize the markers. The first is after a , so starts the conversion. Then converts the rest:
5. Terminalize the markers. The first is after a , so starts the conversion. Then converts the rest:

For example, with and :

Answer: The grammar above generates exactly .

4.3. Construct a CSG for Doubled Words (Lab 12, Task 2)

Define a context-sensitive grammar for

Click to see the solution

Key Concept: Generate the first copy using terminals and the second copy using matching uppercase markers. The markers are initially interleaved with the first copy. Then move all uppercase markers to the right, preserving their order, and finally convert them into terminals.

Use terminals and nonterminals . Let mean “the second-copy symbol corresponding to ” and mean “the second-copy symbol corresponding to ”. The start symbol is .

The grammar is:

1. Generate interleaved pairs. If , then: The lowercase symbols form the first copy in order, and the uppercase symbols form the second copy markers in the same order.
2. Move uppercase markers right across lowercase symbols. The rules , , , and move each marker rightward without changing its identity.
3. Convert the uppercase block left to right. The pair rules , , , and convert an uppercase symbol only when another uppercase symbol follows it. The final or converts the last marker:

The rule handles , so . The special empty-string rule is legal because never appears on the right-hand side of any rule.

Answer: The grammar generates exactly all doubled words over .

4.4. Generate with an Unrestricted Grammar (Lab 12, Example 2)

Generate

using an unrestricted grammar.

Click to see the solution

Key Concept: In an unrestricted grammar, the direct swap is allowed, so the construction is shorter than the strict context-sensitive version.

Use:

For :

Now swap the middle :

Convert markers:

Convert markers:

Answer: The grammar generates exactly for .

4.5. Construct an Unrestricted Grammar for Powers of Two (Lab 12, Task 3)

Generate an unrestricted grammar for

Click to see the solution

Key Concept: Start with two markers. Each iteration doubles the number of markers. Because the grammar is unrestricted, we may use control markers and erase them during the final cleanup.

Use terminals and nonterminals . The grammar is:

Here and are left and right boundary markers. is a doubling head moving right. is a return head moving left. is a finalization marker.

1. Initial configuration. If we immediately finalize by , we get: This gives , corresponding to .
2. Start one doubling pass.
3. Double each while moving right. More clearly, each rule application consumes one old and leaves two markers behind it.
4. When reaches the right boundary, change direction.
5. Move back to the left boundary.
6. Either double again or finalize. Repeating the pass doubles to , then , and so on. Finalization converts all markers into :

Every successful cycle doubles the number of markers, and the only initial number is . Therefore the terminal lengths are exactly .

Answer: The grammar above generates .

4.6. Construct an Unrestricted Grammar for (Lab 12, Task 4)

Generate an unrestricted grammar for

Click to see the solution

Key Concept: This is the same counting pattern as : counts match counts, and counts match counts.

Use:

For and :

Move markers to the right:

Convert markers:

Answer: The grammar generates exactly with .

4.7. Construct a CSG for Equal Numbers of , , and (Homework 12, Task 1)

Define a context-sensitive grammar for

Click to see the solution

Key Concept: First generate one , one , and one for each required triple. Then use swaps to place the markers in any desired order, and finally convert markers into terminals. Since each generated unit contains exactly one of each marker, every terminal word has equal counts.

Use terminals and nonterminals . The grammar is:

1. Generate equal counts. After uses of and one use of , the sentential form contains exactly copies of , copies of , and copies of .
2. Permute markers arbitrarily. The adjacent swap rules let us rearrange any sequence of , , and markers into any other sequence with the same multiset of markers.
3. Match a target word. Suppose the target word is . It has two ’s, two ’s, and two ’s. Generate: Then use swaps to obtain: Finally convert:

Every generated terminal word has equal numbers of , , and because markers are only created in triples. Conversely, any word with equal positive counts can be reached by generating enough triples, permuting the markers into that word’s order, and terminalizing.

Answer: The grammar generates exactly all nonempty strings over with equal counts of , , and .

4.8. Construct an Unrestricted Grammar for (Homework 12, Task 2)

Generate an unrestricted grammar for

Click to see the solution

Key Concept: For every generated , create two markers and three markers. Then move all markers before all markers and terminalize.

Use terminals and nonterminals . The grammar is:

1. Generate the markers. For : This contains two ’s, four markers, and six markers.
2. Move all markers left of all markers. Repeatedly apply :
3. Convert markers into symbols:
4. Convert markers into symbols:

The construction creates exactly two markers and three markers per , so every terminal word has the form .

Answer: The grammar generates exactly .

4.9. Prove the Halting Problem Is Undecidable (Lecture 13, Example 1)

Prove that no Turing Machine can decide, for every machine index and every input , whether machine halts on .

Click to see the solution

Key Concept: Assume a perfect halting decider exists, then use it to build a machine that contradicts itself on its own index.

1. Assume the opposite of what we want to prove. Suppose there is a Turing Machine computing the total function Here means that machine halts on input .

2. Build the diagonal function. Define This function asks what machine does on input and then behaves oppositely: it halts when does not halt on itself, and it loops when halts on itself.

3. Use computability closure. If is computable, then is computable too, because only calls and then performs a simple branch.

4. Assign an index to . Since is computable, there is some machine index such that

5. Evaluate on the self-input . There are two cases.

   If , then by definition of , . But by definition of , . Since , this says the same computation both does not halt and does halt.

   If , then by definition of , . But by definition of , . Again, the same computation both halts and does not halt.

6. Conclude. Both possible outputs of lead to contradiction. Therefore the original assumption that is computable is false.

Answer: The Halting Problem is undecidable: no total computable function can correctly decide halting for all program-input pairs.

4.10. Explain the Programming-Style Halting Contradiction (Lecture 13, Example 2)

Use the intuitive program notation from the lecture to explain why a universal procedure halts cannot exist.

Click to see the solution

Key Concept: A program analyzer that works for all programs must also analyze programs that call the analyzer, including themselves.

1. Assume a perfect analyzer. Suppose halts(p(x)) always answers whether program halts on input : javascript halts(p(x)) = if magical_analysis(p(x)) then yes else no

2. Specialize it to self-input. Define: javascript halts_on_self(p) = if halts(p(p)) then yes else no This asks whether program halts when given its own code as input.

3. Build the opposite program. Define: javascript trouble(p) = if halts_on_self(p) then loop forever else yes If halts on itself, trouble loops. If does not halt on itself, trouble halts.

4. Run trouble on itself. Consider trouble(trouble).

   If halts_on_self(trouble) says yes, then trouble(trouble) loops forever by its own definition. So the yes answer was wrong.

   If halts_on_self(trouble) says no, then trouble(trouble) returns yes and halts. So the no answer was wrong.

5. Conclude. The assumed perfect analyzer must fail on this self-referential input.

Answer: magical_analysis cannot exist, because any universal halting analyzer can be forced into contradiction by a program that does the opposite of the analyzer’s prediction on itself.

4.11. Prove That Every Recursive Set Is Recursively Enumerable (Lecture 13, Example 3)

Prove Theorem 1: if is recursive, then is recursively enumerable.

Click to see the solution

Key Concept: A recursive set has a computable membership test. Use that test to define a total computable function whose image is exactly the set.

1. Handle the empty set. If , then is RE by definition in the lecture.
2. Assume is nonempty. Since , choose some fixed .
3. Use the characteristic function. Since is recursive, its characteristic function is total and computable:
4. Define an enumerating function.
5. Check that is total and computable. It always halts because always halts. It is computable because it only calls and then returns either or the fixed value .
6. Show that the image is exactly . If , then , so every member of appears in the image. If , then , and is already in . Therefore no value outside appears.

Answer: is the image of a total computable function, so is recursively enumerable.

4.12. Prove the Complement Characterization of Recursive Sets (Lecture 13, Example 4)

Prove Theorem 2:

Click to see the solution

Key Concept: One semidecision procedure gives yes answers for . A second semidecision procedure gives yes answers for the complement. Running both in parallel gives a full decision procedure.

Forward direction: assume is recursive.

1. Since is recursive, Theorem 1 gives that is RE.
2. Since is recursive, is computable. Define the characteristic function of the complement:
3. This function is total and computable, so is recursive.
4. By Theorem 1 again, is RE.

Therefore, if is recursive, both and are RE.

Backward direction: assume and are RE.

1. Since is RE, there is an enumeration:
2. Since is RE, there is an enumeration:
3. To decide whether input belongs to , run both enumerations in parallel:
4. Because and partition , the value must eventually appear in exactly one of the two enumerations.
5. If appears in the enumeration, answer yes. If appears in the complement enumeration, answer no.

This procedure always halts, so is recursive.

Answer: A set is decidable exactly when both it and its complement are semidecidable. As a corollary, recursive sets are closed under complement.

4.13. Explain Why All Total Computable Functions Cannot Be RE-Captured Exactly (Lecture 13, Task 1)

The lecture states that there is no RE formalism that defines all computable total functions and only them. Explain the diagonalization idea.

Click to see the solution

Key Concept: If all total computable functions could be effectively listed, we could construct a new total computable function that differs from every function on the list.

1. Assume an exact RE formalism exists. Suppose there is an effective enumeration of all and only total computable functions:
2. Build a diagonal function. Define a new function
3. Check totality. Every in the enumeration is total by assumption, so is defined for every . Therefore is defined for every , so is total.
4. Check computability. Because the enumeration is effective and each listed function is computable, the diagonal construction can compute and then add . Thus is computable.
5. Derive the contradiction. Since is total and computable, it should appear somewhere in the enumeration. Suppose . Evaluate both at input : But if , then also These two equalities imply , impossible.

Answer: No recursively enumerable formalism can enumerate exactly all total computable functions. Any attempted complete enumeration can be diagonalized against.

4.14. Derive in the Tutorial CSG (Tutorial 14, Example 1)

Using the tutorial context-sensitive grammar, derive .

Click to see the solution

Key Concept: The tutorial grammar first creates , then uses context-sensitive swaps to collect all markers before all markers.

The rules are:

1. Generate three symbols and three marker pairs.
2. Swap each bad pair into . The tutorial uses: Therefore:
3. Convert the block.
4. Convert the block.

Answer: , so the grammar generates the word for .

4.15. Derive in the Tutorial Unrestricted Grammar (Tutorial 14, Example 2)

Using the tutorial unrestricted grammar, derive .

Click to see the solution

Key Concept: The unrestricted grammar can use the direct swap , so the derivation is shorter than in the CSG case.

The grammar is:

Derive:

Swap the middle :

Convert symbols:

Convert symbols:

Answer: .

4.16. Derive with an Unrestricted Grammar (Tutorial 14, Example 3)

Using the tutorial grammar, derive for

Click to see the solution

Key Concept: Generate one , one , and one obligation for each . Then reorder the markers into and terminalize from left to right.

The grammar is:

For :

Now reorder the second block’s , , and markers into global block order:

Convert markers:

Convert markers:

Convert markers:

Answer: .